class Solution {
public:
    vector<int> diffWaysToCompute(string expression) {
        int len = expression.length();
        return dfs(expression, 0, len - 1);
    }

    vector<int> dfs(string expression, int l, int r)
    {
        vector<int> res;
        for(int i = l; i <= r; ++i)
        {
            if(expression[i] >= '0' and expression[i] <= '9')
                continue;
            else
            {
                vector<int> left = dfs(expression, l, i - 1);
                vector<int> right = dfs(expression, i + 1, r);
                for(auto le: left)
                {
                    for(auto ri: right)
                    {
                        int tmp = 0;
                        if(expression[i] == '+')
                            tmp = le + ri;
                        if(expression[i] == '-')
                            tmp = le - ri;
                        if(expression[i] == '*')
                            tmp = le * ri;
                        res.emplace_back(tmp);
                    }
                }
            }
        }
        if(res.empty())
        {
            int tmp = 0;
            for(int i = l; i <= r; ++i)
            {
                tmp = tmp * 10 + (expression[i] - '0');
            }
            res.emplace_back(tmp);
        }
        return res;
    }
};